package algocasts;

import java.util.Stack;

public class P130_VerifyPreorderSequenceInBinarySearchTree {
    private boolean verify(int[] nums, int start, int end) {
        if (start == end || start + 1 == end) return true;
        int root = nums[start];
        int i = start + 1;
        while (i < end && nums[i] < root) ++i;
        int mid = i;
        while (i < end && nums[i] > root) ++i;
        if (i == end) return verify(nums, start + 1, mid) && verify(nums, mid, end);
        else return false;
    }

    // Time: O(n^2)  Space: O(n)
    public boolean verifyPreorderDivideConquer(int[] preorder) {
        if (preorder == null) return false;
        return verify(preorder, 0, preorder.length);
    }

    // Time: O(n)  Space: O(n)
    public boolean verifyPreorderStack(int[] preorder) {
        if (preorder == null) return false;
        Stack<Integer> stack = new Stack<>();
        int lowerBound = Integer.MIN_VALUE;
        for (int num : preorder) {
            if (num < lowerBound) return false;
            while (!stack.isEmpty() && num > stack.peek())
                lowerBound = stack.pop();
            stack.push(num);
        }
        return true;
    }

}
